/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package ordenamiento;

/**
 *
 * @author ANDRES
 */

import java.io.BufferedReader;
import java.io.EOFException;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.ObjectInputStream;
import java.io.PrintWriter;


public class MergeSort 
{
	public static int menu()throws IOException


	{
		System.out.println("________Ordenamiento_______\n");
		System.out.println("1.	ordenamiento mergesort ");
		System.out.println("2.	ordenamiento quickrandomsort ");
		System.out.println("3. 	salir ");
		System.out.println("  opcion  ");
		
		
		int menu;
		menu=LeerNumero();
		return menu;
	
	
	}

	public static void main(String[] args) throws IOException
	{
		int opc=0;
		
			
		
		while (opc!=3)
		{
			try
			
			{
				opc=menu();
				switch (opc)
				{
					case 1:
							leerTextoPlano();
							break;
		
					case 2:leerTextoPlano1();
					       break;
							

					
					case 3:
						System.out.println("fin del programa");
				}
			}
			
			
			
			catch(NumberFormatException objE)
			{
				System.out.println("Ud. ha ingresado un caracter en vez de un número");
			}
			catch(IOException e) 
			{ 
				System.out.println("Error: problemas con la lectura de teclado"); 
			}
		
		}
		
		

	}
	
     //fin del main
     
    public static void leerTextoPlano()
    {
    	  File archivo = null;
       FileReader fr = null;
       BufferedReader br = null;

    	     try {
          // Apertura del fichero y creacion de BufferedReader para poder
          // hacer una lectura comoda (disp1oner del metodo readLine()).
          archivo = new File ("c:/temp/tmp.txt");
          fr = new FileReader (archivo);
          br = new BufferedReader(fr);

          // Lectura del fichero
          String linea;
          
          
          FileWriter fichero = new FileWriter("c:/temp/prueba.txt");
          PrintWriter pw = new PrintWriter(fichero);
          
          
          while((linea=br.readLine())!=null)
          {
         	 String[] arr=linea.split(";");
              int a[]=new int[arr.length];
              for (int i=0; i<arr.length; i++)
              {
         	 System.out.println(arr[i]);
         	 
              }
         	 for (int i=0; i<arr.length; i++)
                a[i] = Integer.parseInt(arr[i]);
         	 
         	 
         	 System.out.println("*********");
         	
         	mergeSort(a);
         	
         	for (int i=0; i<arr.length; i++)
         	{
         	System.out.println(a[i]);
        	 
         	 		pw.println("**************");
         	 		
         	 		pw.println(a[i]);
                     
                      
         	}
                       }
                       pw.close();
                       fr.close(); 
                       
                    	}
    	     
              	   	catch(FileNotFoundException e){}
                 		catch(IOException e){ System.out.println(e);}
                 		
                 }
    
    public static void leerTextoPlano1()
    {
    	  File archivo = null;
       FileReader fr = null;
       BufferedReader br = null;

    	     try {
          // Apertura del fichero y creacion de BufferedReader para poder
          // hacer una lectura comoda (disp1oner del metodo readLine()).
          archivo = new File ("c:/temp/tmp.txt");
          fr = new FileReader (archivo);
          br = new BufferedReader(fr);

          // Lectura del fichero
          String linea;
          
          
          FileWriter fichero = new FileWriter("c:/temp/prueba.txt");
          PrintWriter pw = new PrintWriter(fichero);
          
          
          while((linea=br.readLine())!=null)
          {
         	 String[] arr=linea.split(";");
              int a[]=new int[arr.length];
              for (int i=0; i<arr.length; i++)
              {
         	 System.out.println(arr[i]);
         	 
              }
         	 for (int i=0; i<arr.length; i++)
                a[i] = Integer.parseInt(arr[i]);
         	 
         	 
         	 System.out.println("*********");
         	
         	ordenacionRapida(a);
         	
         	for (int i=0; i<arr.length; i++)
         	{
         	System.out.println(a[i]);
        	 
         	 		pw.println("**************");
         	 		
         	 		pw.println(a[i]);
                     
                      
         	}
                       }
                       pw.close();
                       fr.close(); 
                       
                    	}
    	     
              	   	catch(FileNotFoundException e){}
                 		catch(IOException e){ System.out.println(e);}
                 		
                 }
    public static void ordenacionRapida(int[] v) {
        final int N = v.length;
        quickSort(v,0,N-1);
    }
 
    public static void quickSort(int[] v, int inicio, int fin) {
        if(inicio>=fin) return ;
        int pivote = v[inicio];
        int izq    = inicio+1;
        int der    = fin;
        while(izq<=der) {
            while(izq<=fin   && v[izq]< pivote) izq++;
            while(der>inicio && v[der]>=pivote) der--;
            if(izq<der) {
                int tmp = v[izq];
                v[izq]  = v[der];
                v[der]  = tmp;
            }
        }
        if(der>inicio) {
            int tmp  = v[inicio];
            v[inicio]= v[der];
            v[der]   = tmp;
        }
        quickSort(v,inicio, der-1);
        quickSort(v, der+1, fin);
    }
    public static void mergeSort( int arr[ ]){
        int tmpArray[] = new int[ arr.length ];

        mergeSort( arr, tmpArray, 0, arr.length - 1 );
    }
    private static void mergeSort( int a[ ], int tmpArray[],int left, int right ){
        if( left < right )
        {
            int center = ( left + right ) / 2;
            mergeSort( a, tmpArray, left, center );
            mergeSort( a, tmpArray, center + 1, right );
            merge( a, tmpArray, left, center + 1, right );
        }
    }

    private static void merge( int a[ ],int tmpArray[],int leftPos, int rightPos, int rightEnd){
        int leftEnd = rightPos - 1;
        int tmpPos = leftPos;
        int numElements = rightEnd - leftPos + 1;

        // Main loop
        while( leftPos <= leftEnd && rightPos <= rightEnd ){
            if( a[ leftPos ]<( a[ rightPos ] ) ){
                tmpArray[ tmpPos++ ] = a[ leftPos++ ];
            }
            else{
                tmpArray[ tmpPos++ ] = a[ rightPos++ ];
            }
        }
        while( leftPos <= leftEnd ){    // Copy rest of first half
            tmpArray[ tmpPos++ ] = a[ leftPos++ ];
        }
        while( rightPos <= rightEnd ){  // Copy rest of right half
            tmpArray[ tmpPos++ ] = a[ rightPos++ ];
        }
        // Copy TmpArray back
        for( int i = 0; i < numElements; i++, rightEnd-- ){
            a[ rightEnd ] = tmpArray[ rightEnd ];
        }
        
    }
    public static String LeerCadena()throws IOException
	{
		String s=null;
		try{
		
		BufferedReader lee = new BufferedReader(new InputStreamReader(System.in));
		s=lee.readLine();
		}
		catch(IOException e) { System.out.println("Error: problemas con la lectura de teclado"); }
		
		
		
		return s;
	}
    public static int LeerNumero()throws IOException
	{
		return Integer.parseInt(LeerCadena());
	}
}//class MergeSort

